package targetToOffer.sixthDay;

/**
 * @author Godc
 * @description
 */
public class MaxValue {
    public static void main(String[] args) {
        MaxValueSolution s = new MaxValueSolution();
        int[][] ints = {{1,2,5}, {3,2,1}};
        int i = s.maxValue(ints);
        System.out.println(i);
    }
}
class MaxValueSolution {
    int max = 0;
    public int maxValue(int[][] grid) {
        // 状态定义dp[i][j]表示从起点到ij的最大值
        // 转移方程:dp[i][j] = Max(dp[i-1],[j],dp[i][j-1])+grid[i][j]
        // 状态压缩:直接在原数组上改，不重新建数组
        // 初始化:dp[0][0] = grid[0][0]
        int lx = grid.length;
        int ly = grid[0].length;
        for(int j = 1; j < ly; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < lx; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for (int i = 1; i < lx; i++) {
            for (int j = 1; j < ly; j++) {
                // 初始化第一行和第一列之后无需判断
//                if(i==0&&j==0) continue;
//                else if(i-1<0) grid[i][j] += grid[i][j-1];
//                else if(j-1<0) grid[i][j] += grid[i-1][j];
                grid[i][j] += Math.max(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[lx-1][ly-1];
    }

    /**
     * dfs超时做法
     * @param grid
     * @param x
     * @param y
     * @param res
     */
    public void dfs(int[][] grid,int x,int y,int res){
        res+=grid[x][y];
        if(x==grid.length-1&&y==grid[0].length-1){
            if(res>max) max = res;
            return;
        }
        if(x>=grid.length||y>=grid[0].length) {
            return;
        }
        if(x+1<grid.length) dfs(grid,x+1,y,res);
        if(y+1<grid[0].length) dfs(grid,x,y+1,res);
    }
}